Computer networks are pervasive these days. In a typical computer network, various devices of different types are interconnected via switching elements, such as rooters, switches, and hubs, to allow the devices to communicate among one another according to a predefined communication model.
There are various ways in which networks can be configured into topologies required by applications using those networks. The simplest network tends to involve hardwiring the various devices together using appropriate switching elements and interconnecting media (e.g., conductive cables, fiber optic cables, the wireless medium, etc.). Although the hardwire approach works well for relatively small, static network configurations, it does not scale well and tends to result in networks that are difficult to manage and upgrade.
Recently, there has been proposed a more flexible approach to building computer networks. Instead of constructing each network topology piecemeal by hardwiring the devices together, the devices are viewed as belonging to a common pool of resources, which are disposed in a hierarchical tree topology. A hierarchical tree topology is selected since devices in the tree communicate among themselves along deterministic communication paths, thereby simplifying the provisioning and upgrade tasks. Within the hierarchical tree topology, the devices are interconnected using a pool of switching elements. Depending on how the switching elements are configured, various logical networks can be constructed from this common pool of devices and switching elements (e.g., switches, rooters, and hubs) using, for example, a virtual local area network (VLAN) technology. A discussion of one exemplary VLAN technology may be obtained from the IEEE 802.1Q working group (http://grouper.ieee.org/groups/802/1/, September 2002)
Under this approach, any number of logical network topologies can be constructed from the physical network if there are sufficient resources in the common pool of devices and switching elements (e.g., switches, rooters, and hubs) of the tree. For example, an organization wishes to create or upgrade to a three-tier application topology having two database servers, five application servers, four web servers, and a firewall for Internet access. From this specification and the communication model, which governs the communication policy (including the expected bandwidth usage) for each device required for the application, the necessary devices (e.g., database servers, application servers, web servers, and firewalls) may be picked from the common pool of devices and interconnected using the switching elements in the tree. Thus, the construction of a logical network topology becomes an exercise in picking the required devices from the pool of available devices existing in the tree hierarchy and to configure the switching elements appropriately to interconnect the devices as specified by the communication model and the logical specification. Such a network (containing a variety of devices and network elements so that they comply with a given communication model) is herein referred to as a “farm.”
To facilitate discussion, FIG. 1 illustrates an exemplary data center 100, representing the large common pool of almost 500 networked devices of ten different types and switching elements from which various farms can be constructed. Data center 100 includes a hub 1101 (containing 8 network ports for a total of 4096 Mbps) at the root level of the hierarchical tree. Hub 1101 is coupled with nine rooters 2001, 2002, 2011, 2012, 2013, 2021, 2022, 2023, and 2024, which are disposed at level 1 of the tree (with the hub being level 0).
Router 2001 is coupled with 15 N4000 N-class servers (servers are denoted by the term “cpu” in FIG. 1) and four switches: 8011, 8021, 8031, and 8061, which are disposed at level 2 of the tree. Each of switches 8011, 8021, 8031, and 8061 is coupled to 10 J6000 servers, which are disposed at level 3 of the tree.
Router 2002 is coupled to 25 L3000 servers, which are disposed at level 2 of the tree. As shown in FIG. 1, each of rooters 2011, 2012, and 2013 is coupled to 10 A500 servers, which are disposed at level 2 of the tree.
Router 2021 is coupled to 10 load balancers (1b) and nine switches: 8041, 8051, 8045, 8081, 8001, 8135, 8991, 8981, and 8971, which are disposed at level 2 of the tree. Each of switches 8041, 8051, and 8045 is coupled to 12 LP1000R servers. Each of switches 8081, 8001, and 8135 is coupled to 12 LP2000R servers. Each of switches 8991, 8981, and 8971 is coupled to 8 firewalls. The LP1000R servers, the LP2000R servers, and the firewalls associated with router 2021 are disposed at level 3 of the tree.
Router 2022 is coupled to 10 load balancers (1b) and nine switches: 8042, 8052, 8046, 8082, 8083, 8084, 8992, 8982, and 8972, which are disposed at level 2 of the tree. Each of switches 8042, 8052 and 8046 is coupled to 12 LP1000R servers. Each of switches 8082, 8083 and 8084 is coupled to 12 LP2000R servers. Each of switches 8992, 8982 and 8972 is coupled to 8 firewalls. The LP1000R servers, the LP2000R servers, and the firewalls associated with router 2022 are disposed at level 3 of the tree.
Router 2023 is coupled to 10 load balancers (1b) and five switches: 8043, 8053, 8055, 8085, and 8003, which are disposed at level 2 of the tree. Each of switches 8043, 8053 and 8055 is coupled to 12 LP1000R servers. Each of switches 8085 and 8003 is coupled to 12 LP2000R servers. The LP1000R servers and the LP2000R servers associated with router 2023 are disposed at level 3 of the tree.
Router 2024 is coupled to 10 load balancers (1b) and seven switches: 8044, 8054, 8004, 8005, 8006, 8100 and 8101, which are disposed at level 2 of the tree. Each of switches 8044 and 8054 is coupled to 12 LP 1000R servers. Each of switches 8004, 8005 and 8006 is coupled to 12 LP2000R servers. Switch 8100 is coupled to 6 Virtual Private Network (VPN) gateways (denoted as backhauls in FIG. 1). Switch 8101 is coupled to 4 Network Attached Storage (NAS) facilities and 2 VPN gateways. The LP1000R servers, the LP2000R servers, and the NAS and the VPN gateways associated with router 2024 are disposed at level 3 of the tree.
Suppose one wishes to build a farm from a logical specification that specifies a three-tier architecture having two A500 database servers, one NAS, a cluster of 13 LP2000R application servers, and a VPN gateway (backhaul) from the data center 100 of FIG. 1. Furthermore, the LP2000R application servers do not communicate among one another, nor do the A500 database servers communicate between themselves. The logical specification of this farm is shown in FIG. 2A. The communication model is shown in FIG. 2B. Assuming all the devices in data center 100 are available for use, there is more than sufficient resource in data center 100 to construct the required farm.
If efficiency is not a concern, the farm may be constructed by randomly picking the devices (e.g., the database servers, the LP2000R application servers, and the firewall) from the available devices in the data center 100, and appropriately configuring the switching elements that are disposed along their possible communication paths. However, such a random approach does not optimize the bandwidth usage in data center 100 and may require data among the devices of the farm to traverse more hops than necessary. Consider the communication between a VPN gateway and an LP2000R application server, for example. If both the VPN gateway and the LP2000R application server are picked from those under router 2024, such as under a VPN gateway under switch 8101 and a LP2000R server under switch 8004, the communication between that VPN gateway and the LP2000R server requires only four hops (via switch 8101, router 2024, and switch 8004). On the other hand, if the VPN gateway is picked from those under switch 8100 of router 2024 and the LP2000R server is picked from those under switch 8083 of router 2022, the communication between that VPN gateway and the LP2000R server requires six hops (via switch 8100, router 2024, hub 1101, router 2022, switch 8083). The random approach does not take bandwidth capacity or congestion into consideration when picking the constituent devices.
Another approach known as first-come-first-served (FCFS) dictates that one may traverse the tree in a given direction and gather as much of the resources along the way as possible until all resource requirements are satisfied. Under this approach, the aforementioned farm may be constructed, for example, using resources encountered when traversing through router 2001, its child nodes and its grandchild nodes, and then through router 2002, its child nodes and its grandchild nodes, stopping along the way if and when the required resources are all obtained. Like the random approach, there is little intelligence in the selection of the constituent devices of the farm with respect to bandwidth efficiency. Accordingly, farms constructed using the first-come-first-served paradigm for device selection may also result in bandwidth inefficiency and performance degradation.
The most efficient set of constituent devices to build a farm from a tree topology network may be obtained after evaluating all possible permutations and selecting the most bandwidth efficient permutation. This approach is however impractical for most tree topology networks of any significant size (e.g., having more than 100 devices). Beyond a certain size, the sheer number of devices present in the tree topology network gives rise to an enormous set of possible permutations, which requires a correspondingly enormous amount of computing power and time to evaluate.
Some intelligent device selection algorithms may be employed to reduce the amount of time required to select an efficient set of constituent devices to build a farm. Even though these intelligent device selection algorithms do not require an exhaustive evaluation of all possible combinations in the tree topology network, the amount of time required to come up with a solution nevertheless scales with increasing complexity of the tree network topology. If the tree topology network can be intelligently simplified prior to device selection, these device selection algorithms may work even more efficiently, or may not be required at all to come up with an efficient solution.